Due Mar 16, 3:59 AM EDT
What is the smallest number of colors needed for coloring this graph properly?

On one hand, this graph can be properly colored in 4 colors (actually, this is an instance of the 4-color theorem, but one can also do it manually). On the other hand, 3 colors are insufficient. Take a look at vertex 9. It is surrounded by an odd number of vertices in a cycle (10, 11, 6, 5, 1). In a proper coloring, these vertices will use at least 3 colors. The color of vertex 9 should be distinct from all of them. Thus, we need the 4th color.
Which of the following graphs are bipartite?
Indeed, this graph is bipartite: edges go only between the upper part and the lower one.
In fact, any tree is bipartite: the greedy algorithm for 2-coloring could never fail on a tree, since it tries each vertex only once.
This graph is bipartite, which is established by the following 2-coloring.
